The invention relates to a method for updating a linear feedback shift register of a code generator from a known state to a new state, and to a code generator using the method. xe2x80x98Codexe2x80x99 refers to a pseudo-noise sequence used in a radio system, for instance to a long spreading code or scrambling code in a radio system employing code division multiple access (CDMA).
In radio systems employing code division multiple access, the radio resource is divided on a code-division basis between the various users. The payload of each user is spread onto a wide frequency band, of five megahertz, for instance, by multiplying the payload with a spreading code. A receiver distinguishes the signal it wants by multiplying the received signal by the spreading code used to spread it. Parts of a spreading code are called chips which are, in fact, bits. The value of a chip can be marked by a zero and a one, or in real numbers by a one and a minus one. The chip rate is typically significantly faster, over a hundred times faster, for instance, than the payload rate.
In addition to spreading codes, codes known as scrambling codes can also be used. The scrambling codes do not necessarily spread the signal any more, but scramble the bits of a spread signal by multiplying each bit in the signal with the corresponding scrambling code bit. Scrambling codes can be extremely long, 241xe2x88x921 chips long, for instance.
The spreading codes used are usually as orthogonal as possible with respect to each other. Spreading codes are obtained from a Hadamard matrix, for instance. A Hadamard matrix Mn is an nxc3x97n matrix (n is an even integer) made of zeros and ones so that any matrix line differs from any other matrix line exactly at an n/2 position. One matrix line thus contains only zeros, whereas the rest of the lines contain an equal number of zeros and ones. When n=2, the following Hadamard matrix is obtained:                               M          2                =                  [                                                    0                                            0                                                                    0                                            1                                              ]                                    (        1        )            
From the Hadamard matrix Mn, the Hadamard matrix M2n is generated by the following relation:                               M                      2            ⁢            n                          =                  [                                                                      M                  n                                                                              M                  n                                                                                                      M                  n                                                                                                  M                    _                                    n                                                              ]                                    (        2        )            
where matrix {overscore (M)}n is a complement of matrix Mn, i.e. the zeros have been replaced with ones and the ones with zeros. Thus, matrix 1 provides:                               M          4                =                  [                                                    0                                            0                                            0                                            0                                                                    0                                            1                                            0                                            1                                                                    0                                            0                                            1                                            1                                                                    0                                            1                                            1                                            0                                              ]                                    (        3        )            
Further, maxtrix 3 provides:                               M          8                =                  [                                                    0                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                                                    0                                            1                                            0                                            1                                            0                                            1                                            0                                            1                                                                    0                                            0                                            1                                            1                                            0                                            0                                            1                                            1                                                                    0                                            1                                            1                                            0                                            0                                            1                                            1                                            0                                                                    0                                            0                                            0                                            0                                            1                                            1                                            1                                            1                                                                    0                                            1                                            0                                            1                                            1                                            0                                            1                                            0                                                                    0                                            0                                            1                                            1                                            1                                            1                                            0                                            0                                                                    0                                            1                                            1                                            0                                            1                                            0                                            0                                            1                                              ]                                    (        4        )            
If the elements, that is, zeros and ones, of the above Hadamard matrices are represented by ones and minus ones, then the lines in the Hadamard matrix are orthogonal with respect to each other. If desired, the values could also be inverted, i.e. the zeros changed to ones and the ones to zeros, but this does not change the properties of the matrix. For instance, matrix 1 could also be presented as:             M      2        =          [                                    1                                1                                                1                                0                              ]        ,      xe2x80x83    ⁢            M      2        =          [                                    1                                1                                                1                                              -              1                                          ]      
Each matrix line forms one spreading code. The length of a spreading code varies according to the desired spreading factor. Spreading codes can be numbered, for instance, by indicating the code class of the spreading code and its ordinal number in said code class. The code class can be obtained by the following equation: two to the power of the code class equals the length of the spreading code, i.e. the code class is a binary logarithm of the spreading code. Thus, matrix 4, for instance, has the following spreading codes (subindex denotes the code class and the ordinal number is in brackets):
SPREADINGCODE3(0)={0,0,0,0,0,0,0,0}
SPREADINGCODE3(1)={0,1,0,1,0,1,0,1}
SPREADINGCODE3(2)={0,0,1,1,0,0,1,1}
SPREADINGCODE3(3)={0,1,1,0,0,1,1,0}
SPREADINGCODE3(4)={0,0,0,0,1,1,1,1}
SPREADINGCODE3(5)={0,1,0,1,1,0,1,0}
SPREADINGCODE3(6)={0,0,1,1,1,1,0,0}
SPREADINGCODE3(7)={0,1,1,0,1,0,0,1}
According to prior art, all short spreading codes are stored into the memory of a transceiver. This means that for a code class 8 code, for instance, 256 different 256-chip-long codes are stored into the memory, i.e. the memory requirement is 256xc3x97256 bits, which totals 65536 bits. Shorter spreading codes can be generated from the stored long codes, which means that the spreading codes of lower code classes need not be separately stored.
Spreading codes can be extremely long, 221xe2x88x921 chips long, for instance. This creates the technical problem of being able to generate said code in real-time, since the same sequence is typically used, but different transmitters use it at different stages. Ideally, the generated code sequence would be completely random, but this is not practical, because both the transmitter and the receiver must be able to generate the code sequence used and with the same timing, i.e. phase, too.
Code is generated with a code generator, with a code generator using a linear feedback shift register, for instance. Publication WO 96/36137 discloses a linear feedback shift register that is used for generating an m-sequence (maximal length sequence) to provide a pseudo-noise sequence to be used as a code, the sequence being iterated after 2Nxe2x88x921 cycles, where N represents the number of elements in the feedback shift register. The initial state is always known in linear feedback shift registers, but a problem arises from how to jump from the initial state to an unknown new state. In the solution disclosed in said publication, a transformation matrix corresponding to each jump, or at least to each jump corresponding to a power of two, is stored, which transformation matrix indicates how each element of the initial state should be transformed to obtain the elements of the new state. Thus, for instance, for a spreading code of 241xe2x88x921 chips, 41xc3x9741xc3x9741 (the number of the powers of twoxc3x97the number of the elements in the feedback shift registerxc3x97the length of the feedback shift register) bits are stored, i.e. a total of 68921 bits.
It is an object of the invention to develop a method for generating a spreading code when necessary, whereby memory is not needed for storing each spreading code, and saving memory space in comparison with known methods. This object is achieved by the method disclosed in the following. The method in question is a method for updating the linear feedback shift register of a code generator from a known state to a new state, comprising defining the jumps corresponding to the different powers of two for shifting from a known state to a new state. The method also comprises generating in each jump the feedback shift register obtained as a result of said jump as follows: generating the value of one element of the obtained feedback shift register from the previous state and the pre-stored mask register corresponding to said element, while the mask register determines the elements of the feedback shift register of the previous state, using which elements said element value is generated, and repeating the generation of the value of one feedback shift register element for each remaining obtained feedback shift register element by shifting the mask register to the position of said remaining element and by generating the value of said remaining element of the obtained feedback shift register from the previous state and the shifted mask register.
The invention also relates to a code generator of a radio system, comprising means for defining the jumps corresponding to the different powers of two for updating the linear feedback shift register of a code generator from a known state to a new state. The code generator also comprising: means for generating in each jump the feedback shift register obtained as a result of said jump, comprising means for generating the value of one element of the obtained feedback shift register from the previous state and the pre-stored mask register corresponding to said obtained element, while the mask register determines the elements of the feedback shift register of the previous state, using which elements said obtained element value is generated; means for repeating the generation of the value of one feedback shift register element for each remaining obtained feedback shift register element by shifting the mask register to the position of said remaining element and by generating the value of said remaining element of the obtained feedback shift register from the previous state and the shifted mask register.
Preferred embodiments of the invention are set forth in the dependent claims.
The invention is based on the idea that spreading codes are not stored, but generated when necessary using the powerful calculation method disclosed hereafter. In the calculation method, only the mask register of one element of each power of two is most preferably stored. The rest of the mask registers are generated from the stored mask register. The invention provides a significant memory saving, because it is not necessary to store a mask register for each element of a feedback shift register, i.e. for a spreading code of 241xe2x88x921 chips, for instance, only 41xc3x9741 bits (the number of the different powers of two xc3x97 the length of the feedback shift register), totalling 1681 bits, are stored, which constitutes only 1/41 of the 68921 bits needed in the prior art mentioned above.